package com.poxz.algorithm.template;

import java.util.*;

/**
 * 搜索算法（DFS/BFS）
 *
 * @author poxz
 */
public class SearchAlgorithms {

    // ==================== 深度优先搜索（DFS） ====================

    /**
     * DFS - 递归版本（图/树遍历）
     * 时间复杂度: O(V + E)
     *
     * @param graph   邻接表表示的图
     * @param u       当前节点
     * @param visited 访问标记数组
     */
    static void dfsRecursive(List<Integer>[] graph, int u, boolean[] visited) {
        visited[u] = true;
        System.out.print(u + " ");  // 处理当前节点

        for (int v : graph[u]) {
            if (!visited[v]) {
                dfsRecursive(graph, v, visited);
            }
        }
    }

    /**
     * DFS - 非递归版本（使用栈）
     * 时间复杂度: O(V + E)
     *
     * @param graph   邻接表表示的图
     * @param start   起始节点
     * @param visited 访问标记数组
     */
    static void dfsIterative(List<Integer>[] graph, int start, boolean[] visited) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (visited[u]) continue;

            visited[u] = true;
            System.out.print(u + " ");  // 处理当前节点

            // 逆序压栈，保证遍历顺序与递归一致
            List<Integer> neighbors = graph[u];
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int v = neighbors.get(i);
                if (!visited[v]) {
                    stack.push(v);
                }
            }
        }
    }

    /**
     * DFS - 全排列生成
     * 时间复杂度: O(n!)
     *
     * @param nums   待排列的数组
     * @param path   当前路径
     * @param used   使用标记
     * @param result 结果集合
     */
    static void permutation(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            path.add(nums[i]);
            used[i] = true;
            permutation(nums, path, used, result);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }

    /**
     * DFS - 组合生成 C(n, k)
     * 时间复杂度: O(C(n,k))
     *
     * @param n      范围 [1, n]
     * @param k      选取个数
     * @param start  当前起始位置
     * @param path   当前路径
     * @param result 结果集合
     */
    static void combination(int n, int k, int start, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 剪枝：剩余元素不足
        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            combination(n, k, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }

    /**
     * DFS - N皇后问题
     * 时间复杂度: O(n!)
     *
     * @param n      棋盘大小
     * @param row    当前行
     * @param cols   列占用情况
     * @param diag1  主对角线占用情况
     * @param diag2  副对角线占用情况
     * @param board  棋盘
     * @param result 结果集合
     */
    static void nQueens(int n, int row, boolean[] cols, boolean[] diag1, boolean[] diag2,
                        char[][] board, List<List<String>> result) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) {
                solution.add(new String(r));
            }
            result.add(solution);
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1;
            int d2 = row + col;

            if (cols[col] || diag1[d1] || diag2[d2]) continue;

            board[row][col] = 'Q';
            cols[col] = diag1[d1] = diag2[d2] = true;

            nQueens(n, row + 1, cols, diag1, diag2, board, result);

            board[row][col] = '.';
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }

    // ==================== 广度优先搜索（BFS） ====================

    /**
     * BFS - 图遍历
     * 时间复杂度: O(V + E)
     *
     * @param graph   邻接表表示的图
     * @param start   起始节点
     * @param visited 访问标记数组
     */
    static void bfs(List<Integer>[] graph, int start, boolean[] visited) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            System.out.print(u + " ");  // 处理当前节点

            for (int v : graph[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(v);
                }
            }
        }
    }

    /**
     * BFS - 最短路径（无权图）
     * 时间复杂度: O(V + E)
     *
     * @param graph 邻接表表示的图
     * @param start 起始节点
     * @param n     节点总数
     * @return 从start到各节点的最短距离
     */
    static int[] bfsShortestPath(List<Integer>[] graph, int start, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[start] = 0;

        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            int u = queue.poll();

            for (int v : graph[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    queue.offer(v);
                }
            }
        }
        return dist;
    }

    /**
     * BFS - 层序遍历（记录层数）
     * 时间复杂度: O(V + E)
     *
     * @param graph 邻接表表示的图
     * @param start 起始节点
     * @return 每层的节点列表
     */
    static List<List<Integer>> bfsLevelOrder(List<Integer>[] graph, int start) {
        List<List<Integer>> levels = new ArrayList<>();
        boolean[] visited = new boolean[graph.length];

        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                int u = queue.poll();
                level.add(u);

                for (int v : graph[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        queue.offer(v);
                    }
                }
            }
            levels.add(level);
        }
        return levels;
    }

    /**
     * BFS - 网格迷宫最短路径
     * 时间复杂度: O(m * n)
     *
     * @param grid  网格，0表示可走，1表示障碍
     * @param start 起点 [x, y]
     * @param end   终点 [x, y]
     * @return 最短距离，-1表示不可达
     */
    static int bfsMaze(int[][] grid, int[] start, int[] end) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 上下左右
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{start[0], start[1], 0});  // {x, y, dist}
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1], dist = curr[2];

            if (x == end[0] && y == end[1]) {
                return dist;
            }

            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n
                        && grid[nx][ny] == 0 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny, dist + 1});
                }
            }
        }
        return -1;
    }

    // ==================== 双向BFS ====================

    /**
     * 双向BFS - 从起点和终点同时搜索
     * 适用于已知起点和终点的最短路径问题
     * 时间复杂度: O(b^(d/2))，比单向BFS的O(b^d)快
     *
     * @param graph 邻接表
     * @param start 起点
     * @param end   终点
     * @return 最短距离，-1表示不可达
     */
    static int bidirectionalBFS(List<Integer>[] graph, int start, int end) {
        if (start == end) return 0;

        Set<Integer> q1 = new HashSet<>();
        Set<Integer> q2 = new HashSet<>();
        q1.add(start);
        q2.add(end);

        Set<Integer> visited1 = new HashSet<>();
        Set<Integer> visited2 = new HashSet<>();
        visited1.add(start);
        visited2.add(end);

        int steps = 0;

        while (!q1.isEmpty() && !q2.isEmpty()) {
            // 优化：总是扩展较小的集合
            if (q1.size() > q2.size()) {
                Set<Integer> temp = q1;
                q1 = q2;
                q2 = temp;

                temp = visited1;
                visited1 = visited2;
                visited2 = temp;
            }

            Set<Integer> next = new HashSet<>();
            steps++;

            for (int u : q1) {
                for (int v : graph[u]) {
                    if (q2.contains(v)) {
                        return steps;
                    }
                    if (!visited1.contains(v)) {
                        visited1.add(v);
                        next.add(v);
                    }
                }
            }
            q1 = next;
        }
        return -1;
    }

    // ==================== 记忆化搜索 ====================

    /**
     * 记忆化搜索 - 斐波那契数列示例
     * 时间复杂度: O(n)
     *
     * @param n    第n项
     * @param memo 记忆化数组
     * @return 第n项的值
     */
    static long fibMemo(int n, long[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];

        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    /**
     * 记忆化搜索 - 网格路径数（带障碍）
     * 时间复杂度: O(m * n)
     *
     * @param grid 网格，0表示可走，1表示障碍
     * @param x    当前x坐标
     * @param y    当前y坐标
     * @param memo 记忆化数组
     * @return 从(x,y)到右下角的路径数
     */
    static int gridPathMemo(int[][] grid, int x, int y, int[][] memo) {
        int m = grid.length, n = grid[0].length;

        if (x >= m || y >= n || grid[x][y] == 1) return 0;
        if (x == m - 1 && y == n - 1) return 1;
        if (memo[x][y] != -1) return memo[x][y];

        memo[x][y] = gridPathMemo(grid, x + 1, y, memo)
                + gridPathMemo(grid, x, y + 1, memo);
        return memo[x][y];
    }

    /**
     * 功能测试
     *
     * @param args 命令行参数
     */
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        System.out.println("=== 搜索算法示例 ===\n");

        // 构建测试图
        int n = 7;
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        graph[0].add(1);
        graph[0].add(2);
        graph[1].add(3);
        graph[1].add(4);
        graph[2].add(5);
        graph[2].add(6);

        // DFS测试
        System.out.println("--- DFS遍历 ---");
        System.out.print("递归版本: ");
        dfsRecursive(graph, 0, new boolean[n]);
        System.out.println();

        System.out.print("非递归版本: ");
        dfsIterative(graph, 0, new boolean[n]);
        System.out.println("\n");

        // BFS测试
        System.out.println("--- BFS遍历 ---");
        System.out.print("BFS: ");
        bfs(graph, 0, new boolean[n]);
        System.out.println("\n");

        // 最短路径测试
        System.out.println("--- 最短路径 ---");
        int[] dist = bfsShortestPath(graph, 0, n);
        System.out.println("从节点0到各节点的最短距离: " + Arrays.toString(dist));
        System.out.println();

        // 全排列测试
        System.out.println("--- 全排列 ---");
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = new ArrayList<>();
        permutation(nums, new ArrayList<>(), new boolean[nums.length], permutations);
        System.out.println("数组 " + Arrays.toString(nums) + " 的全排列:");
        for (List<Integer> perm : permutations) {
            System.out.println(perm);
        }
        System.out.println();

        // 组合测试
        System.out.println("--- 组合 C(5,3) ---");
        List<List<Integer>> combinations = new ArrayList<>();
        combination(5, 3, 1, new ArrayList<>(), combinations);
        System.out.println("C(5,3) 的所有组合:");
        for (List<Integer> comb : combinations) {
            System.out.println(comb);
        }
        System.out.println();

        // 网格迷宫测试
        System.out.println("--- 网格迷宫最短路径 ---");
        int[][] maze = {
                {0, 0, 1, 0},
                {0, 0, 0, 0},
                {1, 0, 1, 0},
                {0, 0, 0, 0}
        };
        int shortestPath = bfsMaze(maze, new int[]{0, 0}, new int[]{3, 3});
        System.out.println("从(0,0)到(3,3)的最短路径长度: " + shortestPath);
        System.out.println();

        // 记忆化搜索测试
        System.out.println("--- 记忆化搜索 ---");
        int fibN = 10;
        long[] memo = new long[fibN + 1];
        System.out.println("斐波那契数列第" + fibN + "项: " + fibMemo(fibN, memo));
    }
}

